//
//  142. 重排链表.swift
//  Top600
//
//  Created by rjb on 2021/7/28.
//

import Foundation
class Solution143 {
    // 1. 找到中间节点
    // 2. 反转后面链表
    // 3. 合并链表
    func reorderList(_ head: ListNode?) {
        let mid = midNode(head)
        let midNext = mid?.next
        mid?.next = nil
        
        let reversed = reverseNode(midNext)
        mergeNode(head, reversed)
    }
    // 求一个链表的中点
    func midNode(_ head: ListNode?) -> ListNode? {
        var fast: ListNode?  = head
        var slow: ListNode? = head
        while fast?.next != nil && fast?.next?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        return slow
    }
    // 反转一个链表
    func reverseNode(_ head: ListNode?) -> ListNode? {
        var prev: ListNode?
        var curr: ListNode? = head
        while curr != nil {
            let nextTemp = curr?.next
            curr?.next = prev
            prev = curr
            curr = nextTemp
        }
        return prev
    }
    // 合并两个链表
    @discardableResult
    func mergeNode(_ head1: ListNode?,_ head2: ListNode?) -> ListNode? {
        var p1: ListNode? = head1
        var p2: ListNode? = head2
        
        while p1 != nil {
            // 保存第二个链表
            let toNode = p2
            p2 = p2?.next
            
            // 第一个链表
            let p1next = p1?.next
            p1?.next = toNode
            toNode?.next = p1next
            
            p1 = p1next
        }
        return head1
    }
    static func test() {
        let solution = Solution143()
        let node1 = ListNode(1)
        let node2 = ListNode(2)
        let node3 = ListNode(3)
        let node4 = ListNode(4)
        let node5 = ListNode(5)
        let node6 = ListNode(6)
        let node7 = ListNode(7)
        let node8 = ListNode(8)
        
        node1.next = node2
        node2.next = node3
        node3.next = node4
        node4.next = node5
        node5.next = node6
        node6.next = node7
        node7.next = node8
        
        let result = solution.reorderList(node1)
    }
}
